#include <iostream>
#include <limits>
#include "max_subarray.h"

using namespace std;

void max_subarray(int* array, size_t begin, size_t end,
        size_t& max_begin, size_t& max_end, int& max_sum)
{
    if ( begin + 1 == end )
    {
        max_begin = begin;
        max_end = end;
        max_sum = array[begin];
        return;
    }

    size_t mid = ( begin + end ) / 2;

    size_t left_max_begin;
    size_t left_max_end;
    int left_max_sum;
    
    max_subarray(array, begin, mid,
            left_max_begin, left_max_end, left_max_sum);

    size_t right_max_begin;
    size_t right_max_end;
    int right_max_sum;
    max_subarray(array, mid, end,
            right_max_begin, right_max_end, right_max_sum);

    size_t mid_max_begin;
    size_t mid_max_end;
    int mid_max_sum;

    max_subarray_cross_mid(array, begin, end, mid,
            mid_max_begin, mid_max_end, mid_max_sum);

    if ( left_max_sum >= right_max_sum
            && left_max_sum >= mid_max_sum )
    {
        max_begin = left_max_begin;
        max_end = left_max_end;
        max_sum = left_max_sum;
        return;
    }

    if ( right_max_sum >= mid_max_sum )
    {
        max_begin = right_max_begin;
        max_end = right_max_end;
        max_sum = right_max_sum;
        return;
    }

    max_begin = mid_max_begin;
    max_end = mid_max_end;
    max_sum = mid_max_sum;
}

void max_subarray_cross_mid(int* array, size_t begin, size_t end, size_t mid,
        size_t& max_begin, size_t& max_end, int& max_sum)
{
    //look left
    max_begin = mid - 1;
    int left_current_sum = 0;
    int left_max_sum = numeric_limits<int>::min();

    for ( size_t i = mid - 1; i >= begin; --i )
    {
        left_current_sum += array[i];
        if ( left_current_sum > left_max_sum )
        {
            max_begin = i;
            left_max_sum = left_current_sum;
        }

        if ( begin == 0 && i == 0 )
        {
            break;
        }
    }

    //look right
    max_end = mid + 1;
    int right_current_sum = 0;
    int right_max_sum = numeric_limits<int>::min();

    for ( size_t i = mid; i < end; ++i )
    {
        right_current_sum += array[i];
        if ( right_current_sum > right_max_sum )
        {
            max_end = i + 1;
            right_max_sum = right_current_sum;
        }
    }

    max_sum = left_max_sum + right_max_sum;
}

